package _03LinkedList;

class _03InsertSinglyLinkedList {
    // Singly linked list node in Java
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    Node head;
    // TODO: tail pointer or reference

    // time complexity： O(1)
    // space complexity: O(1)
    // inserts a new node on the front of the list.
    public void push(int data) {
        // allocate new node
        Node newNode = new Node(data);
        // insert
        newNode.next = head;
        head = newNode;
    }

    // time complexity： O(n)
    // space complexity: O(1)
    // insert after
    public void insertAfter(int key, int data) {
        // check head
        if(head == null)
            return;

        // allocate new node
        Node newNode = new Node(data);

        // find key node
        Node temp = head;
        while(temp != null && temp.data != key) {
            temp = temp.next;
        }
        // not found
        if(temp == null) return;

        newNode.next = temp.next;
        temp.next = newNode;
        return;
    }

    // time complexity： O(n)
    // space complexity: O(1)
    // append at the end
    public void append(int data) {
        // allocate new node
        Node newNode = new Node(data);

        // head is null
        if(head == null) {
            head = newNode;
            return;
        }

        // append, find last node
        Node last = head;
        while(last.next != null)
            last = last.next;
        last.next = newNode;
        // newNode.next = null;
        return;

    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        _03InsertSinglyLinkedList list = new _03InsertSinglyLinkedList();

        // insert 9 at the end: 9->null
        list.append(9);
        // insert 8 at beginning: 8->9->null
        list.push(8);
        // insert 2 at the beginning: 2->8->9->null
        list.push(2);
        // insert 3 at the end: 2->8->9->3->null
        list.append(3);
        // insert 5, after 8: 2->8->5->9->3->null
        list.insertAfter(8, 5);
        list.printList();
    }
}

